package main

import "fmt"

// 如何求字符串里的最长回文子串

func main() {
	str := "abcdefgfedxyz"
	t := &test{}
	t.getLongestPalindrome(str)
	fmt.Println(str[t.startIndex : t.startIndex+t.len])

	str = "abcdefgfedxyz"
	t = &test{}
	t.getLongestPalindrome2(str)
	fmt.Println(str[t.startIndex : t.startIndex+t.len])

	str = "abcbax"
	m := &manacher{}
	m.manacher(str)
	if m.center != -1 && m.palindromeLen != -1 {
		if m.palindromeLen%2 == 1 { // 回文字符串长度为奇数
			for i := m.center - m.palindromeLen/2; i <= m.center+m.palindromeLen/2; i++ {
				fmt.Print(string(str[i]))
			}
		} else { // 回文字符串长度为偶数
			for i := m.center - m.palindromeLen/2; i < m.center+m.palindromeLen/2; i++ {
				fmt.Print(string(str[i]))
			}
		}
		fmt.Println()
	} else {
		fmt.Println("查找失败")
	}
}

type test struct {
	startIndex int
	len        int
}

type manacher struct {
	center        int
	palindromeLen int
}

// Manacher 算法*
func (p *manacher) manacher(str string) {
	ll := len(str)
	newLen := 2*ll + 1

	s := make([]rune, newLen) // 插入分隔符后的字符串
	pp := make([]int, newLen)

	id := 0 // 以第 id 个字符为中心的回文字符串最右端的下标最大
	for i := 0; i < newLen; i++ {
		s[i] = '*'
		pp[i] = 0
	}

	for i := 0; i < ll; i++ {
		s[(i+1)*2] = rune(str[i])
	}

	p.center = -1
	p.palindromeLen = -1

	for i := 1; i < newLen; i++ {
		if id+pp[id] > i {
			pp[i] = min(id+pp[id]-i, pp[id*2-i])
		} else {
			pp[i] = 1
		}

		// 向左右两边扩展求最长的回文子串
		for i+pp[i] < newLen && i-pp[i] > 0 && s[i-pp[i]] == s[i+pp[i]] {
			pp[i]++
		}

		// 求出当前更大的回文字符串最右端的下标
		if i+pp[i] > id+pp[id] {
			id = i
		}

		// 求出当前更长的回文字符串
		if pp[i]-1 > p.palindromeLen {
			p.center = (i+1)/2 - 1
			p.palindromeLen = pp[i] - 1
		}
	}
}

// 动态规划法
func (p *test) getLongestPalindrome(str string) {
	ll := len(str)
	if ll < 1 {
		return
	}

	p.startIndex = 0
	p.len = 1

	// 申请额外的存储空间记录查找的历史信息
	historyRecord := make([][]int, ll)
	for i := range historyRecord {
		historyRecord[i] = make([]int, ll)
	}

	// 初始化长度为 1 的回文字符串信息
	for i := 0; i < ll; i++ {
		historyRecord[i][i] = 1
	}

	// 初始化长度为 2 的回文字符串信息
	for i := 0; i < ll-1; i++ {
		if str[i] == str[i+1] {
			historyRecord[i][i+1] = 1
			p.startIndex = i
			p.len = 2
		}
	}

	// 查找从长度为 3 开始的回文字符串
	for pLen := 3; pLen <= ll; pLen++ {
		for i := 0; i < ll-pLen+1; i++ {
			var tmp = i + pLen - 1
			if str[i] == str[tmp] && historyRecord[i+1][tmp-1] == 1 {
				historyRecord[i][tmp] = 1
				p.startIndex = i
				p.len = pLen
			}
		}
	}
}

// 中心扩展法
func (p *test) getLongestPalindrome2(str string) {
	n := len(str)
	if n < 1 {
		return
	}

	for i := range str {
		p.expandBothSide(str, i, i)
		p.expandBothSide(str, i, i+1)
	}
}

// 对于字符串 str，以 c1 和 c2 为中心向两侧扩展寻找回文子串
func (p *test) expandBothSide(str string, c1, c2 int) {
	n := len(str)
	for c1 >= 0 && c2 < n && str[c1] == str[c2] {
		c1--
		c2++
	}

	tmpStartIndex := c1 + 1
	tmpLen := c2 - c1 - 1
	if tmpLen > p.len {
		p.len = tmpLen
		p.startIndex = tmpStartIndex
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
